๐Ÿ‘ฉโ€๐Ÿ’ป 17144. ๋ฏธ์„ธ๋จผ์ง€ ์•ˆ๋…•!

@Seongukbaek Posted April 01, 2022 ยท Updated April 01, 2022 ยท 8 min read

๋ฌธ์ œ

๋ฏธ์„ธ๋จผ์ง€๋ฅผ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์„ฑ๋Šฅ์„ ํ…Œ์ŠคํŠธํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ์ง‘์„ ํฌ๊ธฐ๊ฐ€ Rร—C์ธ ๊ฒฉ์žํŒ์œผ๋กœ ๋‚˜ํƒ€๋ƒˆ๊ณ , 1ร—1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆด๋‹ค. ๊ตฌ์‚ฌ๊ณผ๋Š” ๋›ฐ์–ด๋‚œ ์ฝ”๋”ฉ ์‹ค๋ ฅ์„ ์ด์šฉํ•ด ๊ฐ ์นธ (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์‹ค์‹œ๊ฐ„์œผ๋กœ ๋ชจ๋‹ˆํ„ฐ๋งํ•˜๋Š” ์‹œ์Šคํ…œ์„ ๊ฐœ๋ฐœํ–ˆ๋‹ค. (r, c)๋Š” rํ–‰ c์—ด์„ ์˜๋ฏธํ•œ๋‹ค.

๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋Š” ํ•ญ์ƒ 1๋ฒˆ ์—ด์— ์„ค์น˜๋˜์–ด ์žˆ๊ณ , ํฌ๊ธฐ๋Š” ๋‘ ํ–‰์„ ์ฐจ์ง€ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ์ง€ ์•Š์€ ์นธ์—๋Š” ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๊ณ , (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c์ด๋‹ค.

1์ดˆ ๋™์•ˆ ์•„๋ž˜ ์ ํžŒ ์ผ์ด ์ˆœ์„œ๋Œ€๋กœ ์ผ์–ด๋‚œ๋‹ค.

  1. ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ํ™•์‚ฐ๋œ๋‹ค. ํ™•์‚ฐ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๋Š” ๋ชจ๋“  ์นธ์—์„œ ๋™์‹œ์— ์ผ์–ด๋‚œ๋‹ค.

    • (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€๋Š” ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ํ™•์‚ฐ๋œ๋‹ค.
    • ์ธ์ ‘ํ•œ ๋ฐฉํ–ฅ์— ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๊ฑฐ๋‚˜, ์นธ์ด ์—†์œผ๋ฉด ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.
    • ํ™•์‚ฐ๋˜๋Š” ์–‘์€ Ar,c/5์ด๊ณ  ์†Œ์ˆ˜์ ์€ ๋ฒ„๋ฆฐ๋‹ค.
    • (r, c)์— ๋‚จ์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c - (Ar,c/5)ร—(ํ™•์‚ฐ๋œ ๋ฐฉํ–ฅ์˜ ๊ฐœ์ˆ˜) ์ด๋‹ค.
  2. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์ž‘๋™ํ•œ๋‹ค.

    • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ๋Š” ๋ฐ”๋žŒ์ด ๋‚˜์˜จ๋‹ค.
    • ์œ„์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•˜๊ณ , ์•„๋ž˜์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.
    • ๋ฐ”๋žŒ์ด ๋ถˆ๋ฉด ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ๋ฐ”๋žŒ์˜ ๋ฐฉํ–ฅ๋Œ€๋กœ ๋ชจ๋‘ ํ•œ ์นธ์”ฉ ์ด๋™ํ•œ๋‹ค.
    • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ถ€๋Š” ๋ฐ”๋žŒ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์—†๋Š” ๋ฐ”๋žŒ์ด๊ณ , ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋กœ ๋“ค์–ด๊ฐ„ ๋ฏธ์„ธ๋จผ์ง€๋Š” ๋ชจ๋‘ ์ •ํ™”๋œ๋‹ค.

๋‹ค์Œ์€ ํ™•์‚ฐ์˜ ์˜ˆ์‹œ์ด๋‹ค.

  • ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์— ์นธ์ด ์—†๊ธฐ ๋•Œ๋ฌธ์—, ๋‘ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ํ™•์‚ฐ์ด ์ผ์–ด๋‚ฌ๋‹ค.
  • ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ๋ชจ๋‘ ํ™•์‚ฐ์ด ์ผ์–ด๋‚œ๋‹ค.
  • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๋Š” ์นธ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.

๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.

๋ฐฉ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ์˜ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ๊ตฌํ•ด๋ณด์ž.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— R, C, T (6 โ‰ค R, C โ‰ค 50, 1 โ‰ค T โ‰ค 1,000) ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ R๊ฐœ์˜ ์ค„์— Ar,c (-1 โ‰ค Ar,c โ‰ค 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋œ ๊ณณ์€ Ar,c๊ฐ€ -1์ด๊ณ , ๋‚˜๋จธ์ง€ ๊ฐ’์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์ด๋‹ค. -1์€ 2๋ฒˆ ์œ„์•„๋ž˜๋กœ ๋ถ™์–ด์ ธ ์žˆ๊ณ , ๊ฐ€์žฅ ์œ— ํ–‰, ์•„๋žซ ํ–‰๊ณผ ๋‘ ์นธ์ด์ƒ ๋–จ์–ด์ ธ ์žˆ๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Room { Queue<Pair> dustQueue = new LinkedList<>(); int[][] room; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; int R, C; int cleaner1X, cleaner2X; ... }
  • ๋ฏธ์„ธ ๋จผ์ง€์™€ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค
public int goodByeFineDust(int time) { while(time > 0) { spreadDust(); runCleaner(); time--; } return countDust(); }
  • ์ฝ”๋“œ๋Š” ๋จผ์ง€๋ฅผ ํ™•์‚ฐ์‹œํ‚ค๊ณ , ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋ฅผ ๋™์ž‘์‹œํ‚จ๋‹ค. ์ •ํ•ด์ง„ ์‹œ๊ฐ„์ด ๊ฒฝ๊ณผํ•œ ํ›„, ์ „์ฒด ๋ฏธ์„ธ ๋จผ์ง€๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.
private void spreadDust() {...}
  • Queue ์— ์ €์žฅํ•˜๊ณ  ์žˆ๋Š” ๋ฏธ์„ธ ๋จผ์ง€ ์ขŒํ‘œ๋ฅผ ์ด์šฉํ•ด ๋ฏธ์„ธ ๋จผ์ง€๋ฅผ ํ™•์‚ฐ์‹œํ‚จ๋‹ค.
  • ์ด๋•Œ ์—…๋ฐ์ดํŠธํ•  ๋ฏธ์„ธ ๋จผ์ง€ ์ •๋ณด๋ฅผ int[][] tmp ์— ์ €์žฅํ•˜๊ณ , ํ™•์‚ฐ์ด ๋๋‚œ ์ดํ›„ room ์„ ์—…๋ฐ์ดํŠธํ•œ๋‹ค.
private void runCleaner() {...}
  • ๊ณต๊ธฐ ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ ๋ฐฉํ–ฅ์„ ๋”ฐ๋ผ ์ˆœ์ฐจ์ ์œผ๋กœ ๋ฏธ์„ธ ๋จผ์ง€๋ฅผ ์ด๋™์‹œํ‚จ๋‹ค.
  • ๊ณต๊ธฐ ์ฒญ์ •๊ธฐ ๋ฐ”๋กœ ์•ž ์ขŒํ‘œ๋Š” ํ•ญ์ƒ 0 ์œผ๋กœ ์—…๋ฐ์ดํŠธํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } class Room { Queue<Pair> dustQueue = new LinkedList<>(); int[][] room; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; int R, C; int cleaner1X, cleaner2X; public Room (int R, int C) { this.R = R; this.C = C; room = new int[R][C]; } public int goodByeFineDust(int time) { while(time > 0) { spreadDust(); runCleaner(); time--; } return countDust(); } private void spreadDust() { int[][] tmp = new int[R][C]; while(!dustQueue.isEmpty()) { Pair dust = dustQueue.poll(); int divDust = room[dust.x][dust.y] / 5; int checkSpread = 0; for (int i = 0; i < 4; i++) { int nx = dust.x + rangeX[i]; int ny = dust.y + rangeY[i]; if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue; if (room[nx][ny] == -1) continue; tmp[nx][ny] += divDust; checkSpread++; } tmp[dust.x][dust.y] = tmp[dust.x][dust.y] + room[dust.x][dust.y] - (divDust * checkSpread); } for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (room[i][j] == -1) continue; room[i][j] = tmp[i][j]; } } } private void runCleaner() { int i = 0; for (i = cleaner1X - 2; i >= 0; i--) { room[i + 1][0] = room[i][0]; } for (i = 1; i < C; i++) { room[0][i - 1] = room[0][i]; } for (i = 1; i <= cleaner1X; i++) { room[i - 1][C - 1] = room[i][C - 1]; } for (i = C - 2; i > 0; i--) { room[cleaner1X][i + 1] = room[cleaner1X][i]; } for (i = cleaner2X + 2; i < R; i++) { room[i - 1][0] = room[i][0]; } for (i = 1; i < C; i++) { room[R - 1][i - 1] = room[R - 1][i]; } for (i = R - 2; i >= cleaner2X; i--) { room[i + 1][C - 1] = room[i][C - 1]; } for (i = C - 2; i > 0; i--) { room[cleaner2X][i + 1] = room[cleaner2X][i]; } room[cleaner1X][1] = room[cleaner2X][1] = 0; for (i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (room[i][j] > 0) dustQueue.add(new Pair(i, j)); } } } private int countDust() { int count = 0; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (room[i][j] > 0) count += room[i][j]; } } return count; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int R = line[0], C = line[1], T = line[2]; Room dirtyRoom = new Room(R, C); for (int i = 0; i < R; i++) { dirtyRoom.room[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); if (dirtyRoom.room[i][0] == -1 && dirtyRoom.cleaner1X == 0) { dirtyRoom.cleaner1X = i; dirtyRoom.cleaner2X = i+1; } for (int j = 0; j < C; j++) { if (dirtyRoom.room[i][j] > 0) dirtyRoom.dustQueue.add(new Pair(i, j)); } } br.close(); System.out.println(dirtyRoom.goodByeFineDust(T)); } }

โœ๏ธ Review

  • ๋ฏธ์„ธ๋จผ์ง€๋ฅผ ํ™•์‚ฐ์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์—์„œ ์‹œ๊ฐ„์„ ๋งŽ์ด ๋บ๊ฒผ๋‹ค. ๊ฒฐ๋ก ์ ์œผ๋กœ๋Š” ์ถ”๊ฐ€์ ์ธ ๋ฐฐ์—ด์„ ๋‘๊ณ , ๋ฏธ์„ธ๋จผ์ง€ ํ™•์‚ฐ ์ •๋ณด๋ฅผ ์ €์žฅํ•ด๋‘๊ณ , room ์— ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์ด ํ•„์š”ํ–ˆ๋‹ค.
  • ์‹œ๋ฎฌ๋ ˆ์ด์…˜์€ ๋‹จ์ˆœํ•œ ๋“ฏ ํ•˜๋ฉด์„œ ๋งŽ์€ ์ฝ”๋“œ๋Ÿ‰์„ ์š”๊ตฌํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค...

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/17144

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€